The widespread use of digital processing technology has found its way into a variety of equipment and, in some form, into most industries. In many applications, digital processing technology involves the communication of information in coded form. The information to be sent is first translated to a set of code words and then the information is sent as a sequence of code words over a communications channel for decoding at another terminal.
For effective use of the communications channel, selection of the correct coding scheme can be particularly important. Some coding schemes can be implemented using a relatively small amount of data information and, in many instances, permit effective data compression. For communication environments that are susceptible to various types of interference, however, many seemingly efficient data coding schemes become intolerable. For instance, in a data coding scheme involving synchronization of data bits between the transmitting and receiving terminals, interference such as noise can result in loss of synchronization and require retransmission of the data. The retransmission frustrates the object of being an efficient data coding scheme.
There have been many attempts to develop an efficient data coding scheme that permits some degree of interference without requiring retransmission. Many of these efforts concern variable length coding. Variable length coding, as the name suggests, involves assigning code words of different lengths to the symbols to be transmitted. This type of coding is founded on the observation that space can be saved if the short code words are assigned to the most commonly used symbols. An early example of this coding type is the Morse code, where more frequently-used English letters are assigned a short representation (e.g., e=".multidot.") and less frequently-used letters are assigned a longer representation (e.g., p=".multidot.- -.multidot.").
Another example of variable length coding is the Huffman algorithm. The Huffman algorithm takes into account the probability of each symbol and then assigns variable length codes to them in a manner that minimizes the average code word length. The Huffman code words are all variable length strings of ones and zeros, with the underlying rule that no code word for one symbol is a prefix for the code word of another symbol. Accordingly, variable length coding schemes are designed so that the symbols can be uniquely decoded symbol by symbol, by parsing the concatenation of prefix code words in the forward direction.
The International Telecommunications Union (ITU) recently adopted a reverse variable length coding (RLVC) scheme for use in the H.263+ video compression standard. Reverse variable length coding refers to variable length codes that can be uniquely decoded in two directions. An advantage of decoding from both ends of the transmission sequence is the ability to increase tolerance for errors. A bit error in the middle of the sequence, for example, might prevent decoding beyond the point of the error. Using a RVLC scheme, however, the sequence can be decoded from one end up to the point of the error and then from the other end up to the point of the error. By decoding in this manner, RVLCs increase the tolerance of transmission interference, thereby decreasing the need for retransmission and extensive error-correcting algorithms.
The potential applications for reverse and conventional variable length coding schemes are diverse and, for many applications, it is important to maintain a relatively high degree of tolerance for transmission interference and to minimize the size (e.g., bit length) of the codes for efficiency. Tolerance for transmission interference is typically increased by adding verification or error-correcting data to the transmission sequence. A decoder at the receiving end then uses this added data for integrity verification or for error correction. Unfortunately, these two objectives are inconsistent. By adding the verification or error-correcting data to increase tolerance for transmission errors, the effective size of the codes transmitted is increased rather than minimized.